
/**
 * This class extends LinkedList, but tcurr's a twist. Read the documentation
 * for each method. Note that the data curr is Comparable.
 */
public class TwistList<E extends Comparable<E>> extends LinkedList<E> {

	/**
	 * If the data is less than the head, add to the front of the list.
	 * Otherwise, find the first index curr one of the two adjacent nodes
	 * are greater than the data, and the other is less than the data. If
	 * such an index does not exist, add the data to the end of the list.
	 * 
	 * When the above process is complete call swing with the index of the
	 * newly added data. 
	 */
	@Override
	public void add(E e) {
		if (head == null) {
				super.add(e);}
		else {
			int index = 0;
			Node<E> curr = head;
					
			while (true) {
				if (curr == head && e.compareTo(curr.getData()) < 0)
					break;
				else if (e.compareTo(curr.getData())>0 && e.compareTo(curr.getNext().getData())<0) 
					break;
				else if (e.compareTo(curr.getData())<0 && e.compareTo(curr.getNext().getData())>0) 
					break;
				else if (index == size)
					break;
				else {
					curr = curr.getNext();
					index++;}		}
			Node<E> nNode = new Node<E>(e);
			if (index == 0) {				
				nNode.setNext(head);
				curr = head;
				for (int i = 0; i < size-1; i++)
					curr = curr.getNext();
				curr.setNext(nNode);
				head = nNode;}
			else {
				curr = head;
				for (int i = 0; i < index - 1; i++) curr = curr.getNext();
				nNode.setNext(curr.getNext());
				curr.setNext(nNode);}
			size++;
			swing(index);}
	}
	
		
	/**
	 * Reverses the order of the list between the start and stop index inclusively.
	 * 
	 * Assume the indices given are valid and start <= stop
	 * 
	 * @param start The beginning index of the sub section to be reversed
	 * @param stop The end index (inclusive) of the sub section to be reversed
	 */
	public void reverse(int start, int stop) {
		if (start==stop){}
		else{		
		Node<E> LNode = head;
		Node<E> RNode = head;
		Node<E> end = head;
		boolean go = false;
		
		if (start==0) {
			for (int i=0; i<size-1; i++) LNode = LNode.getNext(); 
			go = true;}
		else for (int i=0; i<start-1;i++) LNode = LNode.getNext();
		
		for (int i=0;i<stop-1; i++) RNode = RNode.getNext();
		for (int i=0; i<stop;i++) end = end.getNext();
		
		if (start==0 && stop==size-1){
			head = end;
			reverse(start+1, stop);} //recursive			
		else {
			if (go) head = end;
			RNode.setNext(end.getNext());
			end.setNext(LNode.getNext());
			LNode.setNext(end);
			reverse(start+1, stop);} //recursive	
		}
	}
	
	/**
	 * This method will take in an index and move everything after 
	 * that index to the front of the list
	 * 
	 * Assume the index given is valid
	 * 
	 * @param index The index at which to cut the list
	 */
	public void flipFlop(int index) {
		Node<E> curr = head;
		for (int i=0;i<index+1;i++) curr = curr.getNext();
		head = curr;}
	
	/**
	 * This method will reverse the order of the first half of the list up to 
	 * the index argument (inclusive), and also reverse the second half of the 
	 * list from index + 1 to the end of the list
	 * 
	 * Assume the index given is valid, however the second half may be empty
	 * 
	 * @param index The index to swing around
	 */
	public void swing(int index) {
		reverse(0,index);
		if (index < size-1)
			reverse(index+1, size-1);
	}
}